// https://www.lintcode.com/problem/reorder-list/my-submissions

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: The head of linked list.
     * @return: nothing
     */
    // 法一：个：每次都取最后一个补到前面来
    // (n - 1) + (n - 3) + ... + 1 = O(n^2)次
    void reorderList(ListNode * head) {
        if (!head || !(head->next) || !(head->next->next)) return;
        ListNode * tmp = head;
        while (tmp->next && tmp->next->next)
        {
            ListNode * ttmp = tmp;
            while (ttmp->next->next) ttmp = ttmp->next;
            ttmp->next->next = tmp->next;
            tmp->next = ttmp->next;
            ttmp->next = NULL;
            tmp = tmp->next->next;
        } 
    }
    // 法二：先找到中点，然后把后半段倒过来，然后前后交替合并。
    // void reorderList(ListNode * head) {
    //     if (!head || !(head->next) || !(head->next->next)) return; //注意判断
    //     ListNode * slow = head;
    //     ListNode * fast = head->next->next; // 让slow慢一步，从而把前半段的结尾改成NULL
    //     while (fast && fast->next)
    //     {
    //         slow = slow->next;
    //         fast = fast->next->next;
    //     }
    //     ListNode * head2 = slow->next;
    //     slow->next = NULL;
    //     ListNode * pre = NULL;
    //     ListNode * tmp = NULL;
    //     while (head2)
    //     {
    //         tmp = head2->next;
    //         head2->next = pre;
    //         pre = head2;
    //         head2 = tmp;
    //     }
    //     ListNode * head1 = head;
    //     head2 = pre;
    //     pre = head1;
    //     while (head1) //重新用dummy node根据奇偶判断构造链表会方便一些
    //     {
    //         tmp = head2->next;
    //         head2->next = head1->next;
    //         head1->next = head2;
    //         pre = head1->next;
    //         head1 = head1->next->next;
    //         head2 = tmp;
    //     }
    //     pre->next = head2; // 不管个数奇偶，总是head1先完。
    // }
};


/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: The head of linked list.
     * @return: nothing
     */
    void reorderList(ListNode* head) {
// Input
// 0->null
// Expected
// 0->null
        if (!head || !head->next || !head->next->next) //重要！
            return;
        ListNode* fast = head->next->next; //让slow慢一步，这样把前半段的结尾置为Null
        ListNode* slow = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* head1 = slow->next;
        slow->next = NULL;
        ListNode* pre = NULL;
        while (head1)
        {
            ListNode* tmp = head1->next;
            head1->next = pre;
            pre = head1;
            head1 = tmp;
        }
        ListNode* tmp = head;
        // while (pre && tmp)
        // {
        //     ListNode* tmp1 = pre->next;
        //     pre->next = tmp->next;
        //     tmp->next = pre;
        //     pre = tmp1;
        //     // tmp = tmp->next;
        //     tmp = tmp->next->next;
        // }
        // Input
        // 2->-1->0->null
        // Expected
        // 2->0->-1->null
        // pre：-1->0->null
        // tmp:2->null
        while (pre && tmp)
        {
                    cout << "p" << pre->val << endl;
            ListNode* tmp1 = pre->next;
            pre->next = tmp->next;
            tmp->next = pre;
            pre = tmp1;
            cout << "t" << tmp->val << endl;
            // tmp = tmp->next;
            if (tmp->next->next)
                tmp = tmp->next->next;
            else
            {
                tmp->next->next = pre;
                return;
            }
        }
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverse(ListNode* head) {
        ListNode* pre = NULL;
        while (head) {
            ListNode* tmp = head->next;
            head->next = pre;
            pre = head;
            head = tmp;
        }
        return pre;
    }
    void reorderList(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* next = slow->next;
        slow->next = NULL;
        ListNode* newHead = reverse(next);
        ListNode* l1 = head;
        ListNode* l2 = newHead;
        while (l1 && l2) {
            ListNode* tmp1 = l1->next;
            ListNode* tmp2 = l2->next;
            l1->next = l2;
            l2->next = tmp1;
            l1 = tmp1;
            l2 = tmp2;
        }
    }
};